| 翻訳と辞書 |
| list coloring ： ウィキペディア英語版 |
list coloring
In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors, first studied by Vizing and by Erdős, Rubin, and Taylor.〔.〕
==Definition==
Given a graph ''G'' and given a set ''L''(''v'') of colors for each vertex ''v'' (called a list), a list coloring is a ''choice function'' that maps every vertex ''v'' to a color in the list ''L''(''v''). As with graph coloring, a list coloring is generally assumed to be proper, meaning no two adjacent vertices receive the same color. A graph is ''k''-choosable (or ''k''-list-colorable) if it has a proper list coloring no matter how one assigns a list of ''k'' colors to each vertex. The choosability (or list colorability or list chromatic number) ch(''G'') of a graph ''G'' is the least number ''k'' such that ''G'' is ''k''-choosable.
More generally, for a function ''f'' assigning a positive integer ''f''(''v'') to each vertex ''v'', a graph ''G'' is ''f''-choosable (or ''f''-list-colorable) if it has a list coloring no matter how one assigns a list of ''f''(''v'') colors to each vertex ''v''. In particular, if for all vertices ''v'', ''f''-choosability corresponds to ''k''-choosability.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「list coloring」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|